1. Field of the Invention
The present invention relates to a pattern recognition system which recognizes input data of characters, images, waveforms and the like, and particularly identifies image data to be any one of inferred patterns.
2. Description of the Prior Art
With a recent drastic progress in the computer application technology, various beneficial technical innovation are under way in the field of image processing techniques dealing with characters, figures, photographs, and the like. One of the fundamentals is the improved pattern recognition technique. The computerized pattern recognition technique is applied to the extensive technical fields including character recognition and process, geometric figure recognition and process, voice recognition and process, industrial robot sight function, bionics, and the like.
The most primitive method of pattern recognition is "pattern matching" in which two patterns are aligned and the degree of their matching is measured in terms of a correlation function or the like. The pattern alignment is based on a template which is a pattern representing a class or category. Accordingly, this pattern matching method is to measure the degree of matching between an unknown pattern and the template of each class; therefore it is also called "template matching".
A conventional pattern recognition system uses the above-mentioned template matching method, and this method is described in detail in publication "Digital Image Process Engineering" by Yoshikazu Dezuka, Tadahiro Kitahashi and Hideo Ogawa, pp. 107-111, published on June 15, 1985 by Nikkan Kogyo Shinbun. The pattern recognition system using this method consists of an arithmetic unit 1, a memory 2 and a template memory 3 as shown in the block diagram of FIG. 1. The arithmetic unit 1 measures the degree of matching between the data stored in the memory 2 and the data stored in the template memory 3. The memory 2 stores an initial binary image data of a drawing on which a specific pattern is identified. The template memory 3 stores the above-mentioned template data.
Next, the operation of the above-mentioned pattern recognition system will be described with reference to FIGS. 2A, 2B and 2C. In the case of identifying a pattern 4 shown in FIG. 2A, a template data 5 shown in FIG. 2B is set in the template memory 3, and the template data 5 is collated by the arithmetic unit 1 with binary image data (will be termed "image data" hereinafter) of the drawing stored in the memory 2. The arithmetic unit 1 identifies a pattern on the drawing by examining the degree of matching between values of pixels of the template data 5 and values of pixels in a region 5a of the template data 5 (shown by the dashed block in FIG. 2C) in the image data 6. This operation is implemented for the entirety of the image data 6 by shifting the collating range in the image data 6 by one pixel at a time (indicated by the arrows in FIG. 2C), and the result is stored in the memory 2.
The above template matching method involves the segmentation process for dividing an image into regions corresponding to the object or its constituents in the examination of attributes including the size, shape, concentration, hue and texture of the object in the image data 6, or in the identification of the object by use of the attributes. The image segmentation falls into two methods. The first method is the detection of the edges in the image, and it is intended to clarify the regions of the object by defining the border line which provides the profile of the object. The second method called "region segmentation" is the division of an image based on the assumption that the attribute such as the concentration, hue or texture is constant or varies smoothly within the object. Of the image segmentation processes based on the above template matching method, the first edge detection method is described in the above-mentioned publication "Digital Image Processing Engineering", pp. 72-79, and it will be described in the following with reference to FIGS. 3A and 3B.
In extracting a line of pixels of "1" in the x direction from the image data, the template data 7 as shown in FIG. 3A is set in the template memory 3 and the data 7 is collated with the image data of the drawing stored in the memory 2 by the arithmetic unit 1. The arithmetic unit 1 takes correlation between the image data 6 and template data 7 to determine the presence or absence of the line in the image data 6. In other words, in FIG. 3B, where the image data 6 is assumed to have a positional function of I(x, y) and the region 8 of the template data indicated by the dashed block is assumed to have positional coordinates of J(x, y), the arithmetic unit 1 implements the following operation for the template data. ##EQU1##
The result of operation for the above equation (1) is quantized to binary data, and a binary image of the line in the x-axis direction extracted from I(x, y) is obtained. The calculation of equation (1) is implemented for the entirety of the image data 6 by moving the region 8 of template data by one pixel at a time on the image data 6. J(x, y) obtained as a result of the operation or the binary image obtained by quantization is stored in the memory 2.
A determination process by a conventional pattern recognition system for more intricate patterns is described in detail in publication entitled "Introduction to Computer Image Processing", pp. 148-153, written by Takashi Matsuyama in this part under the supervision of Hideyuki Tamura, edited by Nihon Kogyo Gijutsu Center and published on Mar. 10, 1985 by Souken Shuppan.
This process for recognizing an intricate pattern will be described in brief with reference to FIGS. 4A-4E and FIGS. 5A-5C. In recognizing a specific pattern 10 shown in FIG. 4A by the template matching method, template data 11 (shown in FIG. 4B) is set in the template memory 3, and it is collated by the arithmetic unit 1 with initial binary image data 6 (shown in FIG. 5A) of the object stored in the memory 2. In such a case of recognizing an intricate pattern as the pattern 10, partial pattern templates 12 and 13 derived from the pattern 10 are introduced and the presence of the pattern 10 is determined from the total recognition results for the templates 12 and 13.
FIG. 4E shows reference pixels O, O.sub.1 and O.sub.2 of the pattern 10. The reference pixel O represents the template data 11 shown in FIG. 4B, the reference pixel O.sub.1 represents the partial pattern template 12 shown in FIG. 4C, and the reference pixel O.sub.2, represents the partial pattern template 13 shown in FIG. 4D.
Template matching with the pattern templates 12 and 13 will be described with reference to FIGS. 5A, 5B and 5C. For the image data 6 shown in FIG. 5A, template matching with the partial pattern templates 12 and 13 shown in FIGS. 4C and 4D results in binary data indicative of the partial pattern locations as shown in FIGS. 5B and 5C. These points shown in FIGS. 5B and 5C are pixels b.sub.1, b.sub.2, c.sub.1 and c.sub.2 as a result of recognition for both partial patterns. In general, a pattern is recognized using partial patterns of n in number.
For the partial pattern location binary data B.sub.ei (x, y) indicative of the presence of the i-th partial pattern at coordinates A(x, y) in the object image data, if the reference pixel of the partial pattern i exists at pixel (x, y), it results in B.sub.ei (x, y)=1; otherwise, B.sub.ei (x, y)=0. Determination of the object pattern is made through the judgement of the final pattern location binary data B.sub.ee for all pixels basing on the following equation (2), with a partial pattern reference pixel having coordinates (x.sub.i, y.sub.i) with respect to the reference pixel of the object pattern. ##EQU2##
The partial patterns 12 and 13 of FIGS. 4C and 4D produce coordinates A(x, y), B.sub.e1 (x.sub.1, y.sub.1) and B.sub.e2 (x.sub.2, y.sub.2) of the object image data, and (x.sub.1, y.sub.1) and (x.sub.2, y.sub.2) become the reference pixels O.sub.1 and O.sub.2 with respect to the reference pixel O.
Since the equation (2) involves summation of n times, the number of operations for a field of 1000-by-1000 pixels is 1,000,000.times.n, and this means that the arithmetic unit 1 with an ability of 1,000,000 operational cycles per second, for example, expends n seconds. Namely, for n=2 it takes 2 seconds, and for n=4 it takes 4 seconds to achieve the operational result.
However, the foregoing conventional pattern recognition system having the structure as mentioned above and operating in the template matching manner as described above expends enormous time for the arithmetic operation implemented by the arithmetic unit in order to identify a specific pattern in image data. For example, when the template data 5 in the example of FIG. 1 and FIGS. 2A-2C includes 1000-by-1000 pixels, the number of operations needed will be approximately 1,000,000,000 times, and the total operation will take 1,000 seconds with the arithmetic unit 1 having an arithmetic ability of 1,000,000 operational cycles per second.
In another example of FIG. 1 and FIGS. 3A-3B, if the template data 7 has 3-by-3 pixels and the image data 6 has 1000-by-1000 pixels, the number of operations will be 9,000,000 times. Accordingly, the arithmetic unit 1 having an ability of 1,000,000 operational cycles per second will expend 9 seconds for the matching process.
In order to reduce the time consumption for the operation, it necessitates a proprietary hardware device as disclosed in article entitled "Development of LSI for Binary Image Matching" by Ishikawa and Hoshino, in the proceeding of the 1986 national convention of Institute of Electronics and Communication Engineers of Japan, lecture number 1295.
Beside the above publication, prior art references (written in English) on pattern recognition based on the template matching method are as follows:
(1) A. Rosenfeld & A. C. Kak: "Digital Picture Processing", 2nd edition, Academic Press (1982), Section 9.4 (Vol. 2, pp. 36-49); Section 10.3.1 and 10.3.2 (Vol. 2, pp. 113-121) PA1 (2) E. L. Hall: "Computer Image Processing and Recognition", Academic Press (1979), Section 8.1.2-4 (pp. 480-487) PA1 (3) G. J. Vanderbrug & A. Rosenfeld: "Two-Stage Template Matching", IEEE Transactions on Computers, (Vol. c-26, No. 4, pp. 384-393) PA1 (4) Philip M. Merlin and David J. Farber: "A Parallel Mechanism for Detecting Curves in Pictures", IEEE Transactions on Computers, Vol. C-24, January 1975, pp. 96-98.